package cn.mayday.algorithms.year2021.month1.优先搜索二叉搜索;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
 *
 *
 *
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 *
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 *
 * 返回：
 *
 * [3,9,20,15,7]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Mayday05
 * @date 2021/1/7 9:35
 */
public class Off32ILevelOrder {


    public static void main(String[] args) {
        Integer[] input1 = {3, 9, 20, null, null, 15, 7};
//        Integer[] result = new Off32LevelOrder().levelOrder();
    }

    // 方法一：BFS 广度优先遍历（重点在于队列）
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            result.add(treeNode.val);

            if (treeNode.left != null) {
                queue.add(treeNode.left);
            }
            if (treeNode.right != null) {
                queue.add(treeNode.right);
            }
        }
        int[] resultArray = new int[result.size()];


        int i = 0;
        for (Integer temp : result) {
            resultArray[i] = temp;
            i++;
        }
        return resultArray;
    }


    // 方法二：DFS （重点在于递归）




    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


}
